﻿////////////////#include<iostream>
////////////////#include<string>
////////////////using namespace std;
////////////////class role {
////////////////public:
////////////////	void tong(role*enme)
////////////////	{
////////////////		enme->hp -= 10;
////////////////		if (enme->hp <= 0)
////////////////		{
////////////////			printf("%s输了\n", enme->role1);
////////////////			return;
////////////////		}
////////////////		enme->rage_value += 5;
////////////////		cout << role1 << "捅了" << enme->role1 << "一刀" << enme->role1 << "剩余" << enme->hp << "点血" << endl;
////////////////	}
////////////////	void knere(role*enme)
////////////////	{
////////////////		if (rage_value >= 5)
////////////////		{
////////////////			enme->hp -= 15;
////////////////		}
////////////////		else
////////////////		{
////////////////			cout << "你的怒气值不够无法发动本次砍击" << endl;
////////////////			return;
////////////////		}
////////////////		if (enme->hp <= 0)
////////////////		{
////////////////			cout << enme->role1 << "输了"<<endl;
////////////////			return;
////////////////		}
////////////////		enme->rage_value += 5;
////////////////		cout << role1 << "砍了" << enme->role1 << "一刀" << enme->role1 << "剩余" << enme->hp << "点血" << endl;
////////////////	} 
////////////////	void prin()
////////////////	{
////////////////		cout <<"角色名称："<< role1 <<"剩余血量" <<hp<<"怒气值："<<rage_value<< endl;
////////////////	}
////////////////	void recover()
////////////////	{
////////////////		if (rage_value >=10)
////////////////		{
////////////////			rage_value -= 10;
////////////////			hp += 5;
////////////////			cout << role1 << "吃了一口药恢复了5点血量还剩下" << hp << "点血" << endl;
////////////////		}
////////////////		else
////////////////		{
////////////////			cout << "你的怒气值不够" << endl;
////////////////		}
////////////////		return;
////////////////	}
////////////////	role(string _role1,int _hp,int _range_value)
////////////////	{
////////////////		role1 = _role1;
////////////////		hp = _hp;
////////////////		rage_value = _range_value;
////////////////	}
////////////////	int get_hp()
////////////////	{
////////////////		return hp;
////////////////	}
////////////////private:
////////////////	string role1;
////////////////	int hp;
////////////////	int rage_value;
////////////////};
////////////////int main()
////////////////{
////////////////	role* o1 = new role("独孤求败", 100, 20);
////////////////	role* o2 = new role("东方不败", 150, 0);
////////////////	o1->prin();
////////////////	o2->prin();
////////////////	printf("游戏开始\n");
////////////////	int t1 = 1;
////////////////	int t2 = 1;
////////////////	while (t1 && t2)
////////////////	{
////////////////		cout << "一号选手选择 ";
////////////////		cin >> t1;
////////////////		if (t1 == 1)
////////////////		{
////////////////			o1->tong(o2);
////////////////		}
////////////////		else if (t1 == 2)
////////////////		{
////////////////			o1->knere(o2);
////////////////		}
////////////////		else if (t1 == 3)
////////////////		{
////////////////			o1->recover();
////////////////		}
////////////////		cout << "二号选手选择 ";
////////////////		cin >> t2;
////////////////		if (t2 == 1)
////////////////		{
////////////////			o2->tong(o1);
////////////////		}
////////////////		else if (t2 == 2)
////////////////		{
////////////////			o2->knere(o1);
////////////////		}
////////////////		else if (t2 == 3)
////////////////		{
////////////////			o2->recover();
////////////////		}
////////////////		if (o1->get_hp() == 0)
////////////////		{
////////////////			t1 = 0;
////////////////		}
////////////////		else if (o2->get_hp() == 0)
////////////////		{
////////////////			t2 = 0;
////////////////		}
////////////////	}
////////////////	return 0;
////////////////}
//////////////
//////////////
//////////////
//////////////
//////////////
//////////////#include<iostream>
//////////////#include<string>
//////////////using namespace std;
//////////////template<typename t>
//////////////class vec {
//////////////public:
//////////////	vec()
//////////////		:a(new t[10])
//////////////	{
//////////////		;
//////////////		
//////////////	}
//////////////		~vec()
//////////////	{
//////////////		delete a;
//////////////		a = NULL;
//////////////	}
//////////////	void check()
//////////////	{
//////////////		t* tmp = (t*)realloc(a, captical * 10);
//////////////		if (tmp == nullptr)
//////////////		{
//////////////			perror("realloc::false");
//////////////			return;
//////////////		}
//////////////		a = tmp;
//////////////		captical *= 10;
//////////////	}
//////////////	void push_back(t x)
//////////////	{
//////////////		if (size == captical)
//////////////		{
//////////////			check();
//////////////		}
//////////////		if (size != captical)
//////////////			a[size++] = x;
//////////////	}
//////////////	t top()
//////////////	{
//////////////		if (size == 0)
//////////////		{
//////////////			exit(0);
//////////////		}
//////////////		return a[0];
//////////////	}
//////////////	void push(int pos, t x)
//////////////	{
//////////////		if (pos > size)
//////////////		{
//////////////			printf("错误\n");
//////////////			exit(0);
//////////////		}
//////////////		if (size == captical)
//////////////		{
//////////////			check();
//////////////		}
//////////////		for (int i = size - 1; i >= pos; i--)
//////////////		{
//////////////			a[i + 1] = a[i];
//////////////		}
//////////////		a[pos] = x;
//////////////	}
//////////////	int get_size()
//////////////	{
//////////////		return size;
//////////////	}
//////////////	void print()
//////////////	{
//////////////		for (int i = 0; i < size; i++)
//////////////		{
//////////////			cout << a[i] << ' ';
//////////////		}
//////////////	}
//////////////	bool empty()
//////////////	{
//////////////		if (size == 0)
//////////////		{
//////////////			return true;
//////////////		}
//////////////		else
//////////////		{
//////////////			return false;
//////////////		}
//////////////	}
//////////////	void swap(t& a, t& b)
//////////////	{
//////////////		t p = a;
//////////////		a = b;
//////////////		b = p;
//////////////	}
//////////////	void reverse()
//////////////	{
//////////////		for (int i = 0, j = size - 1; i < j; i++, j--)
//////////////		{
//////////////			swap(a[i], a[j]);
//////////////		}
//////////////	}
//////////////private:
//////////////	t* a;
//////////////	int size = 0;
//////////////	int captical =10;
//////////////};
//////////////int main()
//////////////{
//////////////	vec<string>q;
//////////////	q.push_back("abc");
//////////////	q.push_back("abc");
//////////////	q.push_back("abc");
//////////////	q.reverse();
//////////////	q.print();
//////////////	return 0;
//////////////}
//////////////
//////////////
////////////
////////////
////////////
////////////#include"test.h"
////////////#include<iostream>
////////////#include<stdlib.h>
////////////#include<string.h>
////////////using namespace std;
////////////void test()
////////////{
////////////	bit::string str("abcd");
////////////	bit::string str2("ab");
////////////	str.swap(str2);
////////////	
////////////}
////////////int main()
////////////{
////////////	//test();
////////////	int i = 0;
////////////	char arr[100]="\/-\\";
////////////	while (i <= 100)
////////////	{
////////////		printf("%c\r", arr[i%5]);
////////////	}
////////////	return 0;
////////////}
//////////
//////////
//////////#include<stdio.h>
//////////int main()//a^a^b^b^c^c^d^d^e=e
//////////{
//////////	//a,b 
//////////	int a = 2;//t=a^b^a//0=a^a //b=b^0//任意一对相同的数字异或结果为0，任何一个数字与0进行异或结果是其本身
//////////	int b = 3;
//////////	a = a ^ b;//a=a^a^b
//////////	b = a ^ b;//b=a^b^b
//////////	a = a ^ b;
//////////	printf("%d %d", a, b);
//////////
//////////	return 0;
//////////}
//////
//////
//////
//////
//////
//////#include<iostream>
//////#include<vector>
//////#include<stack>
//////#include<string>
//////using namespace std;
//////
//////class Solution {
//////public:
//////    string convert(string s, int numRows) {
//////        int n = s.size();
//////        if (numRows == 1 || numRows >= n) {
//////            return s;
//////        }
//////        int numT = 2 * numRows - 2;//一个周期所需要的元素个数
//////        int cowT = numRows - 1;//一个周期的列数
//////        int T = (n + numT - 1) / numT;//总共需要几个周期
//////        int a = T * cowT;
//////        vector<string>nums(1010, string(1010, 0));
//////        for (int i = 0, x = 0, y = 0; i < n; i++)
//////        {
//////            nums[x][y] = s[i];
//////            if (i % T < cowT)
//////            {
//////                x++;
//////            }
//////            else {
//////                x--;
//////                y++;
//////            }
//////        }
//////        string res;
//////        //遍历字符串矩阵
//////        for (auto& row : nums) {
//////            for (char ch : row) {
//////                if (ch) {
//////                    res += ch;
//////                }
//////            }
//////        }
//////        return res;
//////    }
//////};
//////int deleteGreatestValue(vector<vector<int>>& grid) {
//////    stack<int>q;
//////    int ans = 0;
//////    stack<int>qmax;
//////    int maxj;
//////    int n = grid[0].size();
//////    for (int k = 0; k <n; k++)
//////    {
//////        for (int i = 0; i < grid.size(); i++)
//////        {
//////            for (int j = 0; j < grid[i].size(); j++)
//////            {
//////                if (q.empty())
//////                {
//////                    q.push(grid[i][j]);
//////                    maxj = j;
//////                }
//////                if (q.top() < grid[i][j])
//////                {
//////                    q.pop();
//////                    q.push(grid[i][j]);
//////                    maxj = j;
//////                }
//////            }
//////            grid[i].erase(grid[i].begin() + maxj);
//////            if (qmax.empty())
//////            {
//////                int t = q.top();
//////                qmax.push(t);
//////            }
//////            else if (qmax.top() < q.top())
//////            {
//////                qmax.pop();
//////                int t = q.top();
//////                qmax.push(t);
//////            }
//////            while (!q.empty())
//////            {
//////                q.pop();
//////            }
//////        }
//////        ans +=qmax.top();
//////        while (!qmax.empty())
//////        {
//////            qmax.pop();
//////        }
//////    }
//////    return ans;
//////}
//////int main()
//////{
//////    string a;
//////    cin >> a;
//////    Solution p;
//////    cout<<p.convert(a,4);
//////}
////
////
////
////
////#include<iostream>
////using namespace std;
////class A {
////public:
////	void f() { cout << "A::f()" << endl; }
////	int a;
////};
////class B:public A {
////public:
////	void f(int a) { cout << "B::f()" << endl; }
////	int a;
////};
////int main()
////{
////	B a;
////	a.f();
////
////	return 0;
////}
//
//
//
//#include<iostream>
//#include<list>
//using namespace std;
//int main()
//{
//
//	int ar[] = { 0,1, 2, 3, 4,  5, 6, 7, 8, 9 };
//	int n = sizeof(ar) / sizeof(int);
//	list<int> mylist(ar, ar + n);
//	list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5);
//	reverse(mylist.begin(), pos);
//	reverse(pos, mylist.end());
//	list<int>::const_reverse_iterator crit = mylist.crbegin();
//	while (crit != mylist.crend())
//	{
//		cout << *crit << " ";
//		++crit;
//	}
//	cout << endl;
//
//
//	return 0;
//}





